package com.kingwood.algorithm.test;

import java.util.*;

public class DongTaiGuiHua {

    /**
     * 查找接口成功率最优时间段
     * https://fcqian.blog.csdn.net/article/details/127957656
     * @param nums
     * @param minAverageLost
     * @return
     */
    public static String getApiMaxLongRange(int[] nums, int minAverageLost) {
        int n = nums.length;
        int[] preSum = new int[n+1];
        for (int i=1; i<=n; i++) {
            preSum[i] = preSum[i-1] + nums[i-1];
        }

        ArrayList<int[]> ans = new ArrayList<>();
        int maxLen = 0;

        for (int i=0; i<n; i++) {
            for (int j=i+1; i<=n; i++) {
                int sum = preSum[j] - preSum[i];
                int len = j - i;
                int lost = len * minAverageLost;

                if (sum <= lost) {
                    if (len >= maxLen) {
                        if (len > maxLen) {
                            // 如果大于之前的最大长度，则清空
                            ans = new ArrayList<>();
                        }
                        ans.add(new int[] {i, j-1});
                        maxLen = len;
                    }
                }
            }
        }

        if (ans.size() == 0) {
            return "NULL";
        }

        ans.sort((a, b) -> a[0] - b[0]);
        StringJoiner sj = new StringJoiner(" ");
        for (int[] an : ans) {
            sj.add(an[0] + "~" + an[1]);
        }

        return sj.toString();
    }

    /**
     * 数组连续和
     * https://fcqian.blog.csdn.net/article/details/127170844
     * @param arr
     * @param x
     * @return
     */
    public static long getArrayLianxuheGeShu(int[] arr, int x) {
        long ans = 0;
        int len = arr.length;
        int[] preSum = new int[len+1];
        for (int i=1; i<=len; i++) {
            preSum[i] = preSum[i-1] + arr[i-1];
        }

        int l=0;
        int r=l;
        while (r <= len) {
            if (preSum[r] - preSum[l] >= x) {
                ans += len - r + 1;
                l++;
                r = l + 1;
            } else {
                r++;
            }
        }

        return ans;
    }

    public static long getArrayLianxuheGeShu2(int[] arr, int x) {
        int n = arr.length;
        int[] preSum = new int[n+1];

        for (int i=1; i<=n; i++) {
            preSum[i] = preSum[i-1] + arr[i-1];
        }

        int ans = 0;
        int l = 0;
        int r = l;
        while (r <= n) {
            if (preSum[r] - preSum[l] >= x) {
                ans += n - r + 1;
                l++;
                r = l + 1;
            } else {
                r++;
            }
        }

        return ans;
    }

    /**
     * 园区参观路径
     * https://blog.csdn.net/qfc_128220/article/details/134635868
     * @param matrix
     * @param dp
     * @param n
     * @param m
     * @return
     */
    public static long getHowmuchVisitedPath(long[][] matrix, long[][] dp, int n, int m) {
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
               if (matrix[i][j] == 1) {
                   continue;
               }

               if (i > 0) {
                    dp[i][j] = dp[i-1][j];
               }
               if (j > 0) {
                    dp[i][j] = dp[i][j-1];
               }
            }
        }

        return dp[n-1][m-1];
    }


    /**
     * 跳格子3
     * https://fcqian.blog.csdn.net/article/details/135064109*
     * @param n
     * @param scores
     * @param k
     * @return
     */
    public static int getMaxScore(int n, int[] scores, int k) {
        k++;
        int[] dp = new int[n];
        dp[0] = scores[0];

        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(dp[0]);

        for (int i=1; i<Math.min(k, n); i++) {
            dp[i] = queue.getFirst() + scores[i];
            while (queue.size() > 0 && dp[i] > queue.getLast()) {
                queue.removeLast();
            }

            queue.addLast(dp[i]);
        }

        for (int i=k; i<n; i++) {
            if (dp[i-k] == queue.getFirst()) {
                queue.removeFirst();
            }

            dp[i] = queue.getFirst() + scores[i];
            while (queue.size() > 0 && dp[i] > queue.getLast()) {
                queue.removeLast();
            }

            queue.addLast(dp[i]);
        }

        return dp[n-1];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        int x = scanner.nextInt();

//        int[] arr = new int[n];
//        for (int i=0; i<n; i++) {
//            arr[i] = scanner.nextInt();
//        }
//
//        System.out.println(getArrayLianxuheGeShu(arr, x));

//        long[][] matrix = new long[n][x];
//        for (int i=0;i<n;i++) {
//            for (int j=0; i<x;j++) {
//                matrix[i][j] = scanner.nextInt();
//            }
//        }
//
//        if (matrix[0][0] == 1 || matrix[n-1][x-1] == 1) {
//            System.out.println(0);
//            return;
//        }
//
//        long[][] dp = new long[n][x];
//        dp[0][0] = 1;
//        System.out.println(getHowmuchVisitedPath(matrix, dp, n, x));

        int n = Integer.parseInt(scanner.nextLine());
        int[] scores = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int k = Integer.parseInt(scanner.nextLine());
        System.out.println(getMaxScore(n, scores, k));
    }
}
